// Problem:    168
// Title:      Number Rotations
// Date:       16-Nov-2007
// Difficulty: 1
// Fun Rating: 1
// Time:       log(n)
// Space:      1
// Closed:     Y
// Answer:     59206

#define DISPLAY_NUMBER 0

#include <iostream>

void solve_problem_168()
{
#if 0
	const int max_digits = 6;
	const int M = 100000;
	const int M_digits = 5;
#else
	const int max_digits = 100;
#endif

	const int M = 100000;
	const int M_digits = 5;
	const int pow10[6] = {1, 10, 100, 1000, 10000, 100000};

#if DISPLAY_NUMBER
	char digits[max_digits+1] = {0};
	int counter = 0;
#endif

	int sum = 0;

	// Try each possible multiplier
	for (int m = 1; m <= 9; m++)
	{
		// Try each possble last digit
		for (int a0 = 1; a0 <= 9; a0++)
		{
			// Find the smallest n that ends with a0 where R(n)=mn.
			int carry = 0;
			int a = a0;
			int number = a0;
#if DISPLAY_NUMBER
			digits[max_digits-1] = '0'+a0;
#endif
			for (int k = 1; k <= max_digits; k++)
			{
				a = m*a+carry;
				if (a == a0 && carry != a0)
				{
#if DISPLAY_NUMBER
					std::cout << "[" << (++counter) << "] " << (&digits[max_digits-k]) << " * " << m << std::endl;
#endif
					// Computes the sum generated from this n.
					int l = max_digits / k;
					int s = l % M;
					for (int i = 1; i <= (M_digits-1)/k; i++)
					{
						s = (s + (long long)(l-i)*pow10[i*k]) % M;
					}
					s = ((long long)number * s) % M;
					sum = (sum + s) % M;
					break;
				}
				else if (k < max_digits)
				{
					carry = a / 10;
					a %= 10;
					if (k <= M_digits)
					{
						number += a*pow10[k];
					}
#if DISPLAY_NUMBER
					digits[max_digits-k-1] = '0'+a;
#endif
				}
			}
		}
	}

	// Exclude 1-9 from the sum.
	std::cout << (sum - 45) << std::endl;
}
